package org.ruanjj.threesum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> resList = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int first = nums[i];
            //remove repeat
            if(i > 0 && first == nums[i-1]){
                continue;
            }
            for(int j = i+1; j < n; j++){
                int second = nums[j];
                //remove repeat
                if(j > i+1 && second == nums[j-1]){
                    continue;
                }
                int thirdIndex = n-1;
                int target = -(first+second);
                while(nums[thirdIndex] > target && thirdIndex > j){
                    thirdIndex --;
                }

                if(thirdIndex <= j){
                    break;
                }

                if(nums[thirdIndex] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(first);
                    list.add(second);
                    list.add(target);
                    resList.add(list);
                }
            }
        }

        return resList;
    }
}
